#ifndef LEETCODE_CN_CPP_JIANZHI_7_H
#define LEETCODE_CN_CPP_JIANZHI_7_H

#include "utils/tree.h"
#include <algorithm>
#include <vector>

using namespace std;

namespace jianzhi_7
{

class Solution
{
private:
    vector<int> *preorder;
    vector<int> *inorder;
    TreeNode *build(int preI, int preJ, int inI, int inJ)
    {
        auto rootVal = (*preorder)[preI];
        auto root = new TreeNode(rootVal);
        if (preI == preJ)
        {
            return root;
        }
        int rootInorderIndex = distance(
            inorder->begin(), find(inorder->begin(), inorder->end(), rootVal));
        int leftInI = inI, leftInJ = rootInorderIndex - 1;
        int rightInI = rootInorderIndex + 1, rightInJ = inJ;
        int leftCount = leftInJ - leftInI + 1, rightCount = rightInJ - rightInI + 1;
        if (leftInI <= leftInJ)
        {
            root->left = build(preI + 1, preI + leftCount, leftInI, leftInJ);
        }
        if (rightInI <= rightInJ)
        {
            root->right = build(preI + leftCount + 1, preJ, rightInI, rightInJ);
        }
        return root;
    }

public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder)
    {
        if (preorder.empty() || inorder.empty())
        {
            return nullptr;
        }
        this->preorder = &preorder;
        this->inorder = &inorder;
        auto res = build(0, preorder.size() - 1, 0, inorder.size() - 1);
        this->preorder = nullptr;
        this->inorder = nullptr;
        return res;
    }
};

} // namespace jianzhi_7

#endif //LEETCODE_CN_CPP_JIANZHI_7_H
